from random import randint

class Midpoint(object):
    """ Class implementing the midpoint displacement algorithm.
        
        In order to create a diagram (map) with this class, you have to instantiate
        it (only once!) and then call 'createNewDiagram' (how many times you wish)
        from it's object.
        
        Class attribs:
        _size - the size (in cells) of the map (2-D array)
        _maxvalue - the maximum value of the elevation;
        (actually - maximum initial value; the values obtained after fully executing the algorithm may be higher)
        _map - the reference to the map, which will contains heights
        _NIL - the value indicating that the cell containing it wasn't affected by the algorithm
        (therefore you should take great care while choosing maxvalue etc.!)
    """
    
    _size = 100
    _maxvalue = 256
    _map = None
    _NIL = -1
    
    def __init__(self, iSize = 100, iMaxValue = 256):
        """ Init. It sets the size of the grid and the max value
        
            params:
            iSize - the size of the grid (which will be a square with the side's length equal to iSize)
            iMaxValue - the new value of maxvalue
        """
        
        self._size = iSize
        self._maxvalue = iMaxValue
        
    def getSize(self):
        """ The 'getter' method returning the size of the grid.
        """
        return self._size
    
    def setSize(self, iNewSize):
        """ The 'setter' method setting the size of the grid.
        """
        self._size = iNewSize
        
    def getMaxValue(self):
        """ The 'getter' method returning the (initial) maximum value.
        """
        return self._maxvalue
    
    def setMaxValue(self, iNewMax):
        """ The 'setter' method setting the (initial) maximum value.
        """
        self._maxvalue = iNewMax
        
        
    def createNewDiagram(self, iSize = None):
        """ Method that creates new map (2-D array) and populates it with height values.
            The iSize argument is optional. If there is none, then this method uses 
            the attribute _size set inside the class. However, if the iSize is properly
            defined, the _size attribute changes its value to iSize.
            
            params:
            iSize - (optional) the new size of the map
        """
        
        if iSize is not None:
            self._size = iSize
        
        self._map = [[self._NIL for i in range(self._size)] for j in range(self._size)]
        self._doMidPoint()
        
        return self._map
#        


    def _doMidPoint(self):
        """ Method that sets the initial values for midpoint displacement algorithm
            and executes the initial call of the latter.
        """
        
        self._map[0][0]                             = self._maxvalue
        self._map[self._size - 1][0]                = self._maxvalue
        self._map[self._size - 1][self._size - 1]   = self._maxvalue
        self._map[0][self._size - 1]                = self._maxvalue
        
        self._midpoint(0, 0, (self._size - 1), (self._size - 1))
    
    def _midpoint(self, x1, y1, x2, y2):
        """ The implementation of the actual midpoint displacement.
            The arguments are the 'coordinates' of the corners of 
            the square (in the map) on which the method shall be working.
            Example: self._midpoint(0, 0, (self._size - 1), (self._size - 1))
            is the calling the method for a square described by coordinates
            (0, 0) and (N, N), where N is the last index in the array.
            In other words, the code above is the initial call of the algorithm,
            the one executed for the entire map.
            
            params:
            x1 - coordinate X of the first point (the upper left corner of the square)
            y1 - coordinate Y of the first point (the upper left corner of the square)
            x2 - coordinate X of the second point (the lower right corner of the square)
            y2 - coordinate Y of the second point (the lower right corner of the square)
        """
        
        # if the square is too tiny - return
        if((x2 - x1) < 2) and ((y2 - y1) < 2):
            return
           
        dist = x2 - x1 + y2 - y1
        hdist=dist / 2
        
        # find the index in the middle
        midx = (x1 + x2) / 2
        midy = (y1 + y2) / 2
        
        # get the values in the corners
        c1 = self._map[x1][y1]
        c2 = self._map[x2][y1]
        c3 = self._map[x2][y2]
        c4 = self._map[x1][y2]
        
        # if not already defined, work out the midpoints of the corners of
        # the rectangle by means of an average plus a random number.
        if self._map[midx][y1] == self._NIL:
            self._map[midx][y1] = (c1 + c2 + randint(0, dist) - hdist) / 2
             
        if self._map[midx][y2] == self._NIL:
            self._map[midx][y2] = (c4 + c3 + randint(0, dist) - hdist) / 2
            
        if self._map[x1][midy] == self._NIL:
            self._map[x1][midy] = (c1 + c4 + randint(0, dist) - hdist) / 2
            
        if self._map[x2][midy] == self._NIL:
            self._map[x2][midy] = (c2 + c3 + randint(0, dist) - hdist) / 2
    
        # work out the middle point...
        self._map[midx][midy] = (c1 + c2 + c3 + c4 + randint(0, dist) - hdist) / 4
    
        # now divide this rectangle into 4, and call again for each smaller
        # rectangle
        self._midpoint(x1, y1, midx, midy)
        self._midpoint(midx, y1, x2, midy)
        self._midpoint(x1, midy, midx, y2)
        self._midpoint(midx, midy, x2, y2)
    
    
    
#### the code below is just for testing quickly! It's not the actual meaningful
#### part of the class!
#d = Midpoint()
#print d.getMaxValue()
#map = d.createNewDiagram(100)
#for row in map:
#    print row
#    
## optional - representation via matplotlib
#import matplotlib.pyplot as plt
#
#plt.imshow(map)
#plt.show()